package jp.sourceforge.talisman.mds.cluster;

/*
 * $Id: ExchangeMethod.java,v 1.1 2009/09/12 05:06:01 weiwei Exp $
 */

import java.util.HashMap;
import java.util.Map;

import jp.sourceforge.talisman.mds.Item;
import jp.sourceforge.talisman.mds.distance.ItemDistanceCalculator;

/**
 * 
 * @author Haruaki Tamada
 * @version $Revision: 1.1 $ 
 */
class ExchangeMethod extends NonHierarchicalClusteringMethod{
    public ExchangeMethod(ClusteringParameter param) throws ParameterTypeMismatchException{
        super(param);
        if(!(param instanceof NonHierarchicalClusteringParameter)){
            throw new ParameterTypeMismatchException("NonHierarchicalClusteringParameter is required");
        }
    }

    public ExchangeMethod(NonHierarchicalClusteringParameter param){
        super(param);
    }

    @Override
    protected Cluster[] doClustering(Item[] items, ClusteringParameter initParam){
        NonHierarchicalClusteringParameter param = (NonHierarchicalClusteringParameter)initParam;

        Cluster[] clusters = initClusters(items, param);
        ItemDistanceCalculator id = param.getDistanceCalculator();

        Map<Item, Cluster> map = new HashMap<Item, Cluster>();
        for(int i = 0; i < clusters.length; i++){
            for(Item item: clusters[i]){
                map.put(item, clusters[i]);
            }
        }

        boolean flag = true;
        while(flag){
            flag = false;

            double delta = Double.MIN_VALUE;
            int target = -1;
            Item targetItem = null;
            for(int i = 0; i < items.length; i++){
                Cluster cluster = map.get(items[i]);

                double dpjA = 0d;
                for(Item item: cluster){
                    if(item != items[i]){
                        dpjA += id.calculate(item, items[i]);
                    }
                }

                for(int j = 0; j < clusters.length; j++){
                    double dpjB = 0d;
                    if(clusters[j] != cluster){
                        for(Item item: clusters[j]){
                            dpjB += id.calculate(item, items[i]);
                        }
                        double d = dpjA - dpjB;
                        if(delta < d){
                            delta = d;
                            target = j;
                            targetItem = items[i];
                        }
                    }
                }
            }
            if(delta > 0d && targetItem != null){
                Cluster cluster = map.get(targetItem);
                cluster.removeItem(targetItem);
                clusters[target].addItem(targetItem);
                map.put(targetItem, clusters[target]);
                flag = true;
            }
        }

        return clusters;
    }
}
